<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>创建二叉搜索树</title>
</head>
<body>
    <script>
        function BinarySearchTree(){
            function Node(key){
                this.key=key;
                this.left=null;
                this.right=null;
            }
            this.root=null;
            this.arr = []
            BinarySearchTree.prototype.insert = function(key){
                if(this.root==null){
                    this.root = new Node(key)
                }else {
                    this._insertNode(this.root,new Node(key));
                }
            }
            BinarySearchTree.prototype._insertNode = function(node,newNode){
               
                    if(node.key>newNode.key){ //左边
                        if(node.left){
                            this._insertNode(node.left,newNode);
                        }else {
                            node.left = newNode
                        }
                    }else { //右边
                        if(node.right){
                            this._insertNode(node.right,newNode);
                        }else {
                            node.right = newNode;
                        }
                    }
                
            }
            // 左序遍历 中左右
            BinarySearchTree.prototype.leftOrderTraversal = function(){
                this._leftOrderTraversalNode(this.root)
            }
            BinarySearchTree.prototype._leftOrderTraversalNode = function(bst){
                console.log(bst.key)
                if(bst.left){
                    this._leftOrderTraversalNode(bst.left)
                }
                if(bst.right){
                    this._leftOrderTraversalNode(bst.right)
                }
            }
             // 中序遍历 左中右
            BinarySearchTree.prototype.middleOrderTraversal = function(){
                this._middleOrderTraversalNode(this.root)
            }
            BinarySearchTree.prototype._middleOrderTraversalNode = function(bst){
                if(bst.left){
                    this._middleOrderTraversalNode(bst.left)
                }
                console.log(bst.key)
                if(bst.right){
                    this._middleOrderTraversalNode(bst.right)
                }
            }
            //右序遍历 左右中
            BinarySearchTree.prototype.rightOrderTraversal = function(){
                this._rightOrderTraversalNode(this.root)
            }
            BinarySearchTree.prototype._rightOrderTraversalNode=function(bst){
                if(bst.left){
                    this._rightOrderTraversalNode(bst.left);
                }
                if(bst.right){
                    this._rightOrderTraversalNode(bst.right);
                }
                console.log(bst.key)
            }
        }
        

        var bst = new BinarySearchTree();
        bst.insert(14);
        bst.insert(6);
        bst.insert(23);
        bst.insert(16);
        bst.insert(3);
        bst.insert(56);
        bst.insert(5);
        bst.insert(8);
        bst.insert(13);
        bst.insert(34);
        // console.log(bst);
        bst.leftOrderTraversal();
        console.log('>>>>>>>>>>>>>>>>>>>>>>>>>>')
        bst.middleOrderTraversal();
        console.log('>>>>>>>>>>>>>>>>>>>>>>>>>>')
        bst.rightOrderTraversal();
    </script>
</body>
</html>